# 二叉搜索树中的插入操作: https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# while 循环直接模拟
class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        """
            插入到叶子结点
        """
        if not root:
            return TreeNode(val)
        cur = root
        while cur:
            pre = cur
            if cur.val < val:
                cur = cur.right
            else:
                cur = cur.left
        
        if pre.val < val:
            pre.right = TreeNode(val)
        else:
            pre.left = TreeNode(val)
        
        return root


# 递归写法
class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        """
            递归写法： 我自己的写法， 还可以更简便的写
        """
        if not root: return TreeNode(val)
        
        def insert(node, val):
            if node.val > val:
                if not node.left:
                    node.left = TreeNode(val)
                    return
                else:
                    insert(node.left, val)
            else:
                if not node.right:
                    node.right = TreeNode(val)
                    return
                else:
                    insert(node.right, val)
        
        insert(root, val)
        return root
